package com.demo.java.OD451_500.OD457;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【贪心歌手(C&D卷)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146342430
 */
public class OdMain {
    static class City implements Comparable<City> {
        int income;
        int decrease;

        public City(int income, int decrease) {
            this.income = income;
            this.decrease = decrease;
        }

        @Override
        public int compareTo(City other) {
            return Integer.compare(other.income, this.income);  // 根据收入进行降序排序
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        int T = scanner.nextInt();  // 总天数
        int N = scanner.nextInt();  // 城市数

        int costDays = 0;
        // 读取每个城市的停留天数
        for (int i = 0; i < N + 1; i++) {
            int days = scanner.nextInt();
            costDays += days;
        }

        // 计算剩余天数
        int restDays = T - costDays;

        List<City> cities = new ArrayList<>();
        // 读取每个城市的收入和减少值
        for (int i = 0; i < N; i++) {
            int income = scanner.nextInt();
            int decrease = scanner.nextInt();
            cities.add(new City(income, decrease));
        }

        int income = 0;
        // 在剩余的天数内，选择最优的城市
        for (int i = 0; i < restDays; i++) {
            Collections.sort(cities);  // 根据收入从大到小排序
            if (!cities.isEmpty() && cities.get(0).income > 0) {  // 如果收入大于0
                income += cities.get(0).income;  // 增加收入
                cities.get(0).income -= cities.get(0).decrease;  // 每天收入减少
            }
        }

        System.out.println(income);  // 输出最大收入

        scanner.close();
    }
}